package com.lry.basic.algorithm.simple;

/**
 * @author:刘仁有
 * @desc: 最长公共前缀
 * @email:953506233@qq.com
 * @data:2020/1/3
 */
public class LongestCommonPrefix {
    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"}));
        System.out.println(longestCommonPrefix2(new String[]{"flower","flow","flight"}));
        System.out.println(longestCommonPrefix3(new String[]{"flower","flow","flight"}));
    }
    //取出第一个作为键值，substring做减法（最好是取出最短的字符串作为键值，可以大大减少substring）
    public static String longestCommonPrefix(String[] strs) {
        if(null==strs||strs.length==0)
            return "";
        String prefix = strs[0];
        for(int i=1;i<strs.length;i++){
            while(strs[i].indexOf(prefix)!=0){
                prefix = prefix.substring(0,prefix.length()-1);
                if(prefix.length()==0){
                    return prefix;
                }
            }
        }
        return prefix;
    }

    public static String longestCommonPrefix3(String[] strs) {
        if(null==strs||strs.length==0)
            return "";
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
        for(int i=0;i<strs.length;i++){
            if(strs[i].length()<min){
                min = strs[i].length();
                minIndex = i;
            }
        }
        String prefix = strs[minIndex];
        for(int i=0;i<strs.length;i++){
            if(i!=minIndex)
            while(strs[i].indexOf(prefix)!=0){
                prefix = prefix.substring(0,prefix.length()-1);
                if(prefix.length()==0){
                    return prefix;
                }
            }
        }
        return prefix;
    }

    public static String longestCommonPrefix2(String[] strs) {
        if(null==strs||strs.length==0)
            return "";
        return longestCommonPrefix2(strs,0,strs.length-1);
    }

    public static String longestCommonPrefix2(String[] strs,int left,int right) {
        if(left==right){
            return strs[left];
        }else{
            int mid = (left+right)>>>1;
            String leftStr = longestCommonPrefix2(strs,left,mid);
            String rightStr = longestCommonPrefix2(strs,mid+1,right);
            return commonPrefix(leftStr,rightStr);
        }
    }
    //leetcode,leet
    public static String commonPrefix(String left,String right){
        int min = Math.min(left.length(),right.length());
        for(int i=0;i<min;i++){
            if(left.charAt(i)!=right.charAt(i)){
                return left.substring(0,i);
            }
        }
        return left.substring(0,min);
    }
}
